package targetToOffer.ninthDay;

/**
 * @author Godc
 * @description
 */
public class MovingCount {
    public static void main(String[] args) {
        MovingCountSolution s = new MovingCountSolution();
        int i = s.movingCount(2, 3, 1);
        System.out.println(i);
    }
}
class MovingCountSolution {
    int cnt = 0;
    public int movingCount(int m, int n, int k) {
        boolean visited[][] = new boolean[m][n];
        dfs(m,n,k,0,0,visited);
        return cnt;
    }
    public void dfs(int m,int n,int k,int i,int j,boolean[][] visited){
        if(i<0||i>=m||j<0||j>=n||visited[i][j]||(parseInt(i)+parseInt(j))>k) return;
        cnt++;
        visited[i][j] = true;
        dfs(m,n,k,i+1,j,visited);
        dfs(m,n,k,i-1,j,visited);
        dfs(m,n,k,i,j+1,visited);
        dfs(m,n,k,i,j-1,visited);
    }
    public int parseInt(int i){
        int sum = 0;
        while(i>0){
            sum+=i%10;
            i/=10;
        }
        String s = "s";
        return sum;
    }
}